package com.zlk.algorithm.algorithm.dynamicPlan.PartitionedKnapsack074;

import java.io.*;
import java.util.Arrays;

// 购买足量干草的最小花费
// 有n个提供干草的公司，每个公司都有两个信息
// cost[i]代表购买1次产品需要花的钱
// val[i]代表购买1次产品所获得的干草数量
// 每个公司的产品都可以购买任意次
// 你一定要至少购买h数量的干草，返回最少要花多少钱
// 测试链接 : https://www.luogu.com.cn/problem/P2918
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
public class Code06_BuyingHayMinimumCost {

    public static int MAXN = 101;
    public static int MAXWEIGHT = 5001;

    public static int n, h, maxv, m;

    public static int[] cost = new int[MAXN+1];
    public static int[] val = new int[MAXN+1];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(reader);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        while (in.nextToken()!=-1){
            n = (int) in.nval;
            in.nextToken();
            h = (int) in.nval;
            maxv = 0;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                val[i] = (int) in.nval;
                maxv = Math.max(maxv, val[i]);
                in.nextToken();
                cost[i] = (int) in.nval;
            }
            // 最核心的一句
            // 包含重要分析
            m = h + maxv;
            out.println(compute1());
        }
        out.flush();
        out.close();
        reader.close();
    }

    /**
     * dp[i][j]  1到i编号选择物品（任何编号可以任意买） 至少购买h数量的干草(严格)，返回最少要花多少钱
     *   dp[i-1][j]
     *   dp[i][j-val[i]]+cost[i]
     *
     *   但是存在dp[n][h]没有值，因为可能存在选不到这个重量 物品重量为3 的情况，重量 只会存在3 6 9 中间是没值的
     *   所以dp[n][h]不是目标值，等往后扩充一下，但是扩充多大呢，其实可以累加 物品中最大的重量（这样就不会有漏的情况），这样需要遍历
     *   如果我直接累加单个物品的最大限制就不需要遍历，其实就是空间换时间 所以j的范围就是 t+MAXT
     *
     *
     */
    private static int compute1() {
        int[][] dp = new int[n+1][m+1];
        Arrays.fill(dp, 1, m + 1, Integer.MAX_VALUE);
        for (int i = 1; i <=n ; i++) {
            for (int j =0; j <= m ; j++) {
                dp[i][j] =dp[i-1][j];
                if(j>=val[i] && dp[i][j-val[i]] != Integer.MAX_VALUE ){
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-val[i]]+cost[i]);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        // >= h
        // h h+1 h+2 ... m
        for (int j = h; j <= m; j++) {
            ans = Math.min(ans, dp[n][j]);
        }
        return ans;
    }

    private static int compute2() {
        int[] dp = new int[m+1];
        Arrays.fill(dp, 1, m + 1, Integer.MAX_VALUE);
        for (int i = 1; i <=n ; i++) {
            for (int j =0; j <= m ; j++) {
                if(j>=val[i] && dp[j-val[i]] != Integer.MAX_VALUE ){
                    dp[j] = Math.min(dp[j],dp[j-val[i]]+cost[i]);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        // >= h
        // h h+1 h+2 ... m
        for (int j = h; j <= m; j++) {
            ans = Math.min(ans, dp[j]);
        }
        return ans;
    }
}
